package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/16 9:16
 */
public class C390 {

    // https://leetcode-cn.com/problems/elimination-game/
    // 暴力解, 内存超出限制, 因为用到辅助数组来模拟
    public static int lastRemaining(int n) {
        if (n < 3) return n;

        int[] nums = new int[n];
        int v = 1;
        for (int i = 0; i < n; i++) nums[i] = v++;

        boolean toRight = true;
        int[] ans = process(nums, toRight);
        while (ans.length != 1) {
            toRight = !toRight;
            ans = process(ans, toRight);
        }
        return ans[0];
    }

    // 向右, 向左
    public static int[] process(int[] nums, boolean toRight) {
        int[] ans = new int[nums.length / 2];
        if (toRight) {
            int ni = 1;
            for (int i = 0; i < ans.length && ni < nums.length; i++) {
                ans[i] = nums[ni];
                ni += 2;
            }
        } else {
            int ni = nums.length-2;
            for (int i = ans.length - 1; i >= 0 && ni >= 0; i--) {
                ans[i] = nums[ni];
                ni -= 2;
            }
        }
        return ans;
    }

    public static int lastRemaining2(int n) {
        return n==1 ? 1 : 2*(n/2+1-lastRemaining(n/2));
    }

    // for test
    public static void main(String[] args) {
//        System.out.println(lastRemaining(9));
        for (int i = 1; i <= 200; i++) {
            if(lastRemaining(i) != lastRemaining2(i) ) {
                System.out.println("OOPS");
            }
            System.out.println(i + " : " + lastRemaining(i));
        }
    }

}
